package leetcode.weekly.week340;

import java.util.HashMap;
import java.util.Map;

//Solution2Test
public class Solution2 {

	public long[] distance(int[] nums) {
		int n = nums.length;
		long[] ans = new long[n];
		long[] left = this.f(nums);
		long[] right = this.f1(nums);
		for (int i = 0; i < n; i++) {
			ans[i] = left[i] + right[i];
		}
		return ans;
	}

	private long[] f(int[] nums) {
		int n = nums.length;
		Map<Integer, Integer> cnts = new HashMap<>();
		Map<Integer, Long> total = new HashMap<>();
		Map<Integer, Integer> poses = new HashMap<>();
		long[] h = new long[n];
		for (int i = 0; i < n; i++) {
			int num = nums[i];
			int pos = poses.getOrDefault(num, -1);
			if (pos != -1) {
				h[i] = 1l * (i - pos) * cnts.get(num) + total.get(num);
				cnts.put(num, cnts.get(num) + 1);
				poses.put(num, i);
				total.put(num, h[i]);
			} else {
				cnts.put(num, 1);
				poses.put(num, i);
				total.put(num, 0l);
			}
		}
		return h;
	}

	private long[] f1(int[] nums) {
		int n = nums.length;
		Map<Integer, Integer> cnts = new HashMap<>();
		Map<Integer, Long> total = new HashMap<>();
		Map<Integer, Integer> poses = new HashMap<>();
		long[] h = new long[n];
		for (int i = n - 1; i >= 0; i--) {
			int num = nums[i];
			int pos = poses.getOrDefault(num, -1);
			if (pos != -1) {
				h[i] = 1l * (pos - i) * cnts.get(num) + total.get(num);
				cnts.put(num, cnts.get(num) + 1);
				poses.put(num, i);
				total.put(num, h[i]);
			} else {
				cnts.put(num, 1);
				poses.put(num, i);
				total.put(num, 0l);
			}
		}
		return h;
	}
}
